package SortTable;

//快速排序
public class QuickSort {
    //快速排序
    public static void sort(int[] arr,int low,int high){
        //递归
        if (low<high){
            int partition = partition(arr, low, high);
            sort(arr,low,partition-1);
            sort(arr,partition+1,high);
        }
    }
    //交换顺序表L中子表r【low，high】的记录，枢轴记录到位，并返回其位置，此时它前面的元素关键字均不大于它，它后面的元素关键字均不小于它
    public static int partition(int[] arr,int low,int high){
        arr[0]=arr[low];
        //第一个关键字作为枢轴
        int pivotkey=arr[low];
        while(low<high){
            while(low<high&&arr[high]>=pivotkey){
                --high;
            }
            arr[low]=arr[high];
            while(low<high&&arr[low]<=pivotkey){
                ++low;
            }
            arr[high]=arr[low];
        }
        arr[low]=arr[0];
        return low;
    }
    public static void main(String[] args) {
        int arr[]={-1,4,5,8,9,67,23,45,66,3,4,8};
        sort(arr,1,arr.length-1);
        for (int i = 1; i <arr.length ; i++) {
            System.out.print(arr[i]+" ");
        }
    }
}
